package Demo16;

import java.util.HashMap;

/**
 * 最小覆盖子串
 * https://leetcode.cn/problems/minimum-window-substring/description/
 */

class Solution {
    /**
     * 时间比较优秀的解法
     * @param ss
     * @param tt
     * @return
     */

    public String minWindow(String ss, String tt) {
        int retLen = Integer.MAX_VALUE;
        int retCur = -1;
        int[] hash2 = new int[128];
        char[] t = tt.toCharArray();
        int count2 = 0;
        for(char ch:t) {
            if(hash2[ch] == 0) count2++;
            hash2[ch]++;
        }
        char[] s = ss.toCharArray();
        int[] hash1 = new int[128];
        for(int left = 0,right = 0,count1 = 0;right < ss.length();right++) {
            // 进入窗口,维护 count1
            char in = s[right];
            hash1[in]++;
            if(hash1[in] == hash2[in]) count1++;
            // 判断
            while(count1 == count2) {
                // 更新返回值
                if(right - left + 1 < retLen) {
                    retCur = left;
                    retLen = right - left + 1;
                }
                // 出窗口,维护count
                char out = s[left];
                if(hash1[out] == hash2[out]) count1--;
                hash1[out]--;
                left++;
            }
        }
        return retCur == -1?"":ss.substring(retCur,retCur + retLen);
    }
    public String minWindow1(String ss, String tt) {
        int retLen = Integer.MAX_VALUE;
        int retCur = -1;
        HashMap<Character,Integer> hash2 = new HashMap<>();
        char[] t = tt.toCharArray();
        int count2 = 0;
        for(char ch:t) {
            hash2.put(ch,hash2.getOrDefault(ch,0) + 1);
        }
        char[] s = ss.toCharArray();
        HashMap<Character,Integer> hash1 = new HashMap<>();
        for(int left = 0,right = 0,count = 0;right < ss.length();right++) {
            // 进入窗口,维护 count
            char in = s[right];
            hash1.put(in,hash1.getOrDefault(in,0) + 1);
            if(hash1.get(in) == hash2.getOrDefault(in,0)) count++;
            // 判断
            while(count == hash2.size()) {
                // 更新返回值
                if(right - left + 1 < retLen) {
                    retCur = left;
                    retLen = right - left + 1;
                }
                // 出窗口,维护count
                char out = s[left];
                if(hash1.get(out) == hash2.getOrDefault(out,0)) count--;
                hash1.put(out,hash1.getOrDefault(out,0) - 1);
                if(hash1.get(out) == 0) hash1.remove(out);
                left++;
            }
        }
        return retCur == -1?"":ss.substring(retCur,retCur + retLen);
    }
}
class Demo {
    public static void main(String[] args) {
        Solution solution = new Solution();
        String ret = solution.minWindow("ADOBECODEBANC","ABC");
        System.out.println(ret);
    }
}